package 题目集.归并;

import java.util.Scanner;

//https://www.acwing.com/problem/content/description/1217/
//有个贪心策略：获取前方比自己大的人数，后方比自己小的人数，即是自己交换的次数
//通过归并排序，获取每个人的前方比自己高的人数，后方比自己矮的人数
public class ch02_小朋友排队 {
    static int[][] arr; //0高度,1前方比自己高的人数，2后方比自己矮的人数
    static int[][] temp;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n][3];
        temp = new int[n][3];
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
        }
        mergeSort(0, n - 1);
        long res = 0;
        for (int[] num : arr) {
            long n = (long) num[1] + (long) num[2];
            res += (1 + n) * n / 2;
        }
        System.out.println(res);
    }


    public static void mergeSort(int l, int r) {
        if (l == r) {
            return;
        }
        int m = (l + r) >> 1;
        mergeSort(l, m);
        mergeSort(m + 1, r);
        merge(l, m, r);
    }

    //10
//7 60 15 89 34 40 85 20 72 99
    public static void merge(int l, int m, int r) {
        int a = l, b = m + 1;  //左闭右闭，m是左侧的右边界.所以右侧的起点不包含m
        int i = l;
        while (a <= m && b <= r) {
            if (arr[a][0] > arr[b][0]) {
                arr[b][1] += m - a + 1; //a-m之间的人数，包括a
                temp[i++] = arr[b++];
            } else {
                arr[a][2] += b - m - 1; //b-m之间的人数，不包括b
                temp[i++] = arr[a++];
            }
        }
        while (a <= m) {
            arr[a][2] += r - m; //右侧的所有都比自己小
            temp[i++] = arr[a++];
        }
        while (b <= r) {
            temp[i++] = arr[b++];
        }
        while (l <= r) {
            arr[l] = temp[l];
            l++;
        }
    }
}
